Natural Language Processing

Natural language processing begins with an awkward fact: text is not numbers, and every machine-learning algorithm on the other pages of this site eats numbers. So the first half of the subject is representation — how to turn a document into a vector without throwing away what makes it mean what it means. We climb a ladder of increasingly faithful representations: count the words (bag of words), discount the words that appear everywhere (tf-idf), count short sequences instead of words (n-grams), and finally learn a low-dimensional vector for each word from the company it keeps (embeddings). The second half turns representation into prediction: a language model assigns probabilities to sentences, and regular expressions — the oldest tool on the page — handle the text that must match exactly.

Vectorizers

A vectorizer fixes a vocabulary — the list of distinct tokens seen in a corpus — and represents each document by one number per vocabulary entry. The pages' other models then apply unchanged: a document is a point, and similarity, clustering and classification are geometry.

Bag of Words

Take the sentence: A bag-of-words is a representation of text that describes the occurrence of words within a document. Tokenize it — lowercase, strip the punctuation, split the hyphenated compound — and it becomes 17 tokens. The bag-of-words representation counts them:

  1. Give each distinct word an index, in order of first appearance:
    {'a': 0, 'bag': 1, 'of': 2, 'words': 3, 'is': 4, 'representation': 5, 'text': 6, 'that': 7, 'describes': 8, 'the': 9, 'occurrence': 10, 'within': 11, 'document': 12}
  2. The representation $s$ of a document counts occurrences, $s[i] = $ the frequency of word $i$: 
    s = [3 1 3 2 1 1 1 1 1 1 1 1 1]
    Read it back: a occurs 3 times, of 3 times, words twice, every other word once — and the entries sum to 17, the token count. What the representation keeps is frequency; what it discards, deliberately, is order: every permutation of the sentence has the same vector.

Tf-idf

Raw counts have a flaw across a corpus: the words that occur most (the, data in a data corpus) are usually the words that distinguish least. Tf-idf reweights each count by how rare the word is across documents. For a term $t$ in document $d$, $$\mathrm{tfidf}(t, d) = \mathrm{tf}_{t,d} \cdot \mathrm{idf}_t, \qquad \mathrm{idf}_t = \ln \frac{N}{\mathrm{df}_t},$$ where $\mathrm{tf}_{t,d}$ is the count of $t$ in $d$, $N$ is the number of documents, and $\mathrm{df}_t$ is the number of documents containing $t$. A word in every document gets $\mathrm{idf} = \ln 1 = 0$ and vanishes; a word in one document keeps its full count, scaled by $\ln N$. (Production implementations smooth both factors — scikit-learn, for instance, uses $\ln\frac{1+N}{1+\mathrm{df}_t} + 1$ and often a sublinear $1 + \ln \mathrm{tf}$ — but the reweighting idea is the formula above.)

Worked example, two documents:

The vocabulary is (data, science, uses, to, find, patterns, tests, ideas, with). Here data and science occur in both documents, so their idf is $0$; every other word occurs in one document, so its idf is $\ln 2 \approx 0.693$. Multiplying counts by idf:

d1 = [0, 0, 0.693, 0.693, 0.693, 0.693, 0,     0,     0    ]
d2 = [0, 0, 0,     0,     0,     0,     0.693, 0.693, 0.693]
#        data  science  uses    to     find  patterns tests  ideas  with

Notice what happened to data in $d_1$: it is the most frequent word in the document ($\mathrm{tf} = 2$) and tf-idf still zeroes it, because in this two-document corpus it separates nothing. Tf-idf is a statement about the corpus, not the document — add a third document without data in it and the entry comes back to life.

n-Grams

Bag of words and tf-idf both discard word order, and order carries meaning (dog bites man is not man bites dog). The n-gram fix is to change the token: instead of single words, count consecutive $n$-tuples of words. At $n = 1$ this is exactly bag of words. At $n = 2$ the tokens are bigrams — consecutive pairs. The sentence The n-grams typically are collected from a text or speech corpus has ten bigrams:

['The n-grams', 'n-grams typically', 'typically are',
'are collected', 'collected from', 'from a', 'a text',
'text or', 'or speech', 'speech corpus']

Now score a new sentence against that vocabulary: An apple is typically collected from a tree. Its bigrams are mostly new, but two — collected from and from a — are in the vocabulary, in positions 4 and 5, so its 2-gram representation is

s = [0 0 0 0 1 1 0 0 0 0]

The cost is combinatorial: a vocabulary of $V$ words admits $V^n$ possible n-grams, almost all unseen in any corpus, so count vectors become vast and sparse as $n$ grows. That sparsity is the pressure that pushes the subject from counting toward learning representations — the embeddings of the next section, and the language models after them.

Embeddings

The representations so far give every word its own coordinate axis, so a corpus of $100{,}000$ words produces $100{,}000$-dimensional document vectors — and, worse, geometry that knows nothing: the axes for cat and kitten are exactly as orthogonal as those for cat and democracy. An embedding instead assigns each word a short, dense, learned vector — typically $100$ to $300$ numbers — placed so that words used in similar contexts land near each other. Similarity of meaning becomes similarity of vectors, measured by the cosine $$\cos(v, w) = \frac{v \cdot w}{\lVert v \rVert \, \lVert w \rVert}.$$

Word2vec

Word2vec (Mikolov et al., 2013) learns embeddings from a prediction task nobody actually cares about: guess a word from its neighbours, or its neighbours from it. Each word $w$ carries two vectors — a target vector $v_w$ and a context vector $u_w$: $$\text{apple}\implies \begin{cases} v_{\text{apple}}\\ u_{\text{apple}} \end{cases}$$ In the skip-gram architecture, the probability of seeing context word $o$ in the window around centre word $c$ is a softmax over dot products, $$P(o \mid c) = \frac{\exp(u_o \cdot v_c)}{\sum_{w} \exp(u_w \cdot v_c)},$$ and training maximizes the log-probability of the contexts that actually occur. The mechanism is the point: to predict well, $v_c$ must have large dot products with the context vectors of the words $c$ keeps company with — so words that keep the same company are pulled to nearby vectors. Meaning is never supplied; it is squeezed out of co-occurrence.

The full softmax costs one pass over the vocabulary per training step, so in practice it is replaced by negative sampling: for each true (centre, context) pair, draw $K$ noise words and train a logistic classifier to tell them apart, $$\log \sigma(u_o \cdot v_c) + \sum_{k=1}^{K} \mathbb{E}_{w_k \sim P_n}\big[\log \sigma(-u_{w_k} \cdot v_c)\big], \qquad \sigma(x) = \frac{1}{1 + e^{-x}},$$ where the noise distribution keeps frequent words frequent but flattens them, $P_n(w) \propto \mathrm{count}(w)^{0.75}$. Each positive example pulls $v_c$ toward the true context vectors; each negative pushes it away from vectors it should not resemble:

  1. Positive example: in "The skin of ripe apples is generally red", with a window of radius $L = 3$ around apples, training pulls $v_{\text{apples}}$ toward $u_{\text{skin}}, u_{\text{of}}, u_{\text{ripe}}, u_{\text{is}}, u_{\text{generally}}, u_{\text{red}}$.
  2. Negative examples: $K$ words drawn from $P_n$ — say theorem and highway — contribute the opposite gradient: $v_{\text{apples}}$ is pushed away from their context vectors.

The famous payoff is that the learned geometry encodes relations as directions: $v_{\text{king}} - v_{\text{man}} + v_{\text{woman}}$ lands nearest to $v_{\text{queen}}$ — the "royalty" direction survives subtracting the "male" direction and adding the "female" one. GloVe (Pennington et al., 2014) reaches similar geometry by factoring a global co-occurrence matrix instead of predicting locally. The explorer below is a toy version of exactly this geometry.

Demo: The Embedding Explorer

Eighteen words, each with a two-dimensional embedding built by hand so the relations are exact — real embeddings have hundreds of dimensions and are learned, not drawn, but every computation below is the real one. Click a word to see its nearest neighbours by cosine similarity. Pick two words to compare them, or run an analogy $a - b + c$ and watch where the arithmetic lands.

Analogy
Click a word in the plot.

Three honest caveats. First, two dimensions are a cartoon: real embeddings need their hundreds of dimensions, and projecting them down (by PCA or t-SNE) distorts the neighbourhoods it shows. Second, cosine similarity measures relatedness in the training corpus, not truth — antonyms like hot and cold keep nearly identical company and end up close. Third, the corpus's biases are in the geometry too; the same arithmetic that finds queen also recovers the stereotypes of the text it trained on.

Language Models

A language model assigns a probability to a sequence of words. By the chain rule, $$P(w_1 w_2 \cdots w_T) = \prod_{t=1}^{T} P\big(w_t \mid w_1 \cdots w_{t-1}\big),$$ so modelling text is one repeated task: predict the next word from its history. An n-gram language model truncates the history to the last $n - 1$ words (the Markov assumption) and estimates the conditional by counting, $$P(w_t \mid w_{t-n+1} \cdots w_{t-1}) \approx \frac{\mathrm{count}(w_{t-n+1} \cdots w_t)} {\mathrm{count}(w_{t-n+1} \cdots w_{t-1})}.$$ Models are compared by perplexity, the exponential of the mean negative log-probability per word — intuitively, the model's effective branching factor: a perplexity of $20$ means it is as uncertain as if choosing uniformly among $20$ words at every step.

The counting estimator collapses on unseen n-grams — most grammatical continuations never occur in any finite corpus, and a single zero probability zeroes the whole sentence — so practical n-gram models smooth: reserve a little probability mass for the unseen (add-$k$ smoothing, and more carefully Kneser–Ney). Neural language models dissolve the problem differently: words enter as embeddings, so an unseen sequence of similar words borrows probability from seen ones, and recurrent networks, then transformers, removed the fixed window entirely — attention lets the prediction at position $t$ look back at any earlier position, which is the architecture behind modern large language models (see the transformer section of the Neural Networks page). The task never changed — predict the next word — only the memory and the geometry did.

Regular Expression

A regular expression is a pattern written in a small language of its own: literal characters match themselves, and the operators below repeat, alternate and group them. (The name is the mathematician's: without back-references, a pattern describes exactly a regular language — the kind a finite-state machine can recognise — which is why a match is fast and its cost is easy to predict.) Regular expressions are the oldest tool on this page, and they survive because some text work must be exact rather than probable: pulling a date out of a log line, checking that a field has the right shape, splitting a corpus into tokens, blanking every digit in a transcript. For those jobs a pattern is deterministic, inspectable and needs no training data. Its limits are just as clear: a pattern sees shape, not meaning — it cannot tell a real date from 2026-99-99, which has the same shape — and it is the wrong tool for nested structure such as HTML, which no regular language can describe.

The table below collects the common building blocks. Two details repay attention, because both are frequent sources of wrong matches. First, the anchors ^ and $ match the start and end of the string; they match at line breaks only when the engine's multiline flag is set. Second, the quantifiers are greedy by default — they take as much as they can — and a trailing ? makes one lazy, taking as little as it can; the Examples below show the difference on the same input.

Character Classes
escape
\

            
wildcard
.

            
digit
\d

            
non-digit
\D

            
word
\w

            
non-word
\W

            
whitespace
\s

            
non-whitespace
\S

            
new line
\n

            
tab
\t

    
Assertions
start of string (of a line, with the multiline flag)
^

            
end of string (of a line, with the multiline flag)
$

            
word boundary
\b

            
non-word boundary
\B

            
positive lookahead
x(?=y)

            
negative lookahead
x(?!y)

            
positive lookbehind
(?<=y)x

            
negative lookbehind
(?<!y)x
  


Groups and Ranges
capturing group
(x)

            
non-capturing group
(?:x)

            
or
x|y

            
range
[a-z] [abc]

            
negative range
[^a-z] [^abc]







Quantifiers
0 or more times
*

            
1 or more times 
+

            
0 or 1 times
?

            
n times 
{n}

            
at-least n times
{n,}

            
between n and m times
{n,m}

            
lazy (shortest match)
*? +? ??

Examples

Three worked examples, each on a stated input; every output below was produced by running the pattern, in the two engines the next sections use. They share one running text:

Order 42 shipped on 2026-10-30; order 7 ships on 2026-11-02.
extract datespattern  \b\d{4}-\d{2}-\d{2}\b
matches  ['2026-10-30', '2026-11-02']

# \d{4} is exactly four digits; the \b anchors keep the
# pattern from starting inside a longer digit string.
# Shape only: 2026-99-99 matches too — validate after.
whole wordsinput    The cat sat. The catalog lists cats, not dogs.
pattern  cat     -> ['cat', 'cat', 'cat']   (inside catalog, cats)
pattern  \bcat\b -> ['cat']                 (the standalone word only)
greedy vs lazyinput    <b>bold</b> and <i>ital</i>
pattern  <.*>   -> ['<b>bold</b> and <i>ital</i>']  (one longest run)
pattern  <.*?>  -> ['<b>', '</b>', '<i>', '</i>']   (each tag)

Demo: The Regex Tester

The three examples above, live. Type a pattern — or press an example button — and see where it lands: matches are highlighted in the text and listed with their positions and capture groups. It runs in your browser, on the JavaScript engine of the next section, and trying the greedy pattern first and the lazy one second is the fastest way to feel the difference the table only states.

Examples

Javascript

In JavaScript a regular expression is a built-in object, written either as a literal between slashes (with flags after the closing slash — g for global, i for case-insensitive) or built with the RegExp constructor, which takes the pattern as a string and so needs each backslash doubled.

const re = /\w+\s/g;
// each word together with the space after it

const str = 'fee fi fo fum';
str.match(re);

Outputs : ["fee ", "fi ", "fo "]
// The following two expressions are equivalent
const reLiteral = /\w+\s/g;
const reObject = new RegExp('\\w+\\s', 'g');

// The running text from Examples, same pattern
'Order 42 shipped on 2026-10-30; order 7 ships on 2026-11-02.'
  .match(/\b\d{4}-\d{2}-\d{2}\b/g);
// ["2026-10-30", "2026-11-02"]
        
// Groups are numbered from 1; $1 in the replacement
// is whatever the first group captured.
let input = 'x^cos(y)';
input = input.replace(/\^/g, '**');
input = input.replace(/(cos|sin|tan|sqrt)/g, 'Math.$1');
console.log(input);  // x**Math.cos(y)

re (Python Library)

In Python, regular expressions come from the re library. Write patterns as raw strings (r"...") so a backslash reaches the engine instead of being read as a Python escape first. One distinction decides many bugs: re.match tries the pattern only at the start of the string, while re.search scans for it anywhere. Flags such as re.MULTILINE are passed by keyword — the third positional argument of re.split, for example, is a maximum split count, not a flag.

import re
findall text = "Order 42 shipped on 2026-10-30; order 7 ships on 2026-11-02."

# findall returns every non-overlapping match
re.findall(r"\b\d{4}-\d{2}-\d{2}\b", text)

Outputs : ['2026-10-30', '2026-11-02']
sub # In the replacement, \2 is the second captured group:
# (year)-(month)-(day) is rewritten month/day/year.
re.sub(r"(\d{4})-(\d{2})-(\d{2})", r"\2/\3/\1", text)

Outputs : 'Order 42 shipped on 10/30/2026; order 7 ships on 11/02/2026.'
match vs searchre.match(r"\d+", text)          # None — position 0 is 'O', not a digit
re.search(r"\d+", text).group() # '42' — the first match anywhere

References